package com.code.leetcode._202504;

import java.util.ArrayDeque;
import java.util.Deque;
/***最长的有效的括号，难度困难**/
public class LongestValidParentheses {

    public int longestValidParentheses(String s){
        Deque<Integer> d = new ArrayDeque<>();
        int n = s.length();
        int ans = 0;
        for (int i = 0, j = -1; i < n; i++) {
            //查询到了(进行入栈 有效的括号一定时先(再)
            if (s.charAt(i) == '(') {
                d.addLast(i);
            } else {
                //需要判断是否存在(
                if (!d.isEmpty()) {
                    //去除最后的一个
                    d.pollLast();
                    int top = j;//记录开始位置
                    if (!d.isEmpty()) top = d.peekLast();
                    ans = Math.max(ans, i - top);
                } else {
                    j = i;
                }
            }
        }
        return ans;
    }
}
